\documentclass[numbers=enddot,12pt,final,onecolumn,notitlepage]{scrartcl}% \usepackage[headsepline,footsepline,manualmark]{scrlayer-scrpage} \usepackage[all,cmtip]{xy} \usepackage{amssymb} \usepackage{amsmath} \usepackage{amsthm} \usepackage{framed} \usepackage{comment} \usepackage{color} \usepackage[breaklinks=True]{hyperref} \usepackage[sc]{mathpazo} \usepackage[T1]{fontenc} \usepackage{tikz} \usepackage{needspace} \usepackage{tabls} %TCIDATA{OutputFilter=latex2.dll} %TCIDATA{Version=5.50.0.2960} %TCIDATA{LastRevised=Sunday, October 25, 2020 17:09:13} %TCIDATA{SuppressPackageManagement} %TCIDATA{} %TCIDATA{} %TCIDATA{BibliographyScheme=Manual} %TCIDATA{Language=American English} %BeginMSIPreambleData \providecommand{\U}[1]{\protect\rule{.1in}{.1in}} %EndMSIPreambleData \usetikzlibrary{arrows} \newcounter{exer} \theoremstyle{definition} \newtheorem{theo}{Theorem}[section] \newenvironment{theorem}[1][] {\begin{theo}[#1]\begin{leftbar}} {\end{leftbar}\end{theo}} \newtheorem{lem}[theo]{Lemma} \newenvironment{lemma}[1][] {\begin{lem}[#1]\begin{leftbar}} {\end{leftbar}\end{lem}} \newtheorem{prop}[theo]{Proposition} \newenvironment{proposition}[1][] {\begin{prop}[#1]\begin{leftbar}} {\end{leftbar}\end{prop}} \newtheorem{defi}[theo]{Definition} \newenvironment{definition}[1][] {\begin{defi}[#1]\begin{leftbar}} {\end{leftbar}\end{defi}} \newtheorem{remk}[theo]{Remark} \newenvironment{remark}[1][] {\begin{remk}[#1]\begin{leftbar}} {\end{leftbar}\end{remk}} \newtheorem{coro}[theo]{Corollary} \newenvironment{corollary}[1][] {\begin{coro}[#1]\begin{leftbar}} {\end{leftbar}\end{coro}} \newtheorem{conv}[theo]{Convention} \newenvironment{convention}[1][] {\begin{conv}[#1]\begin{leftbar}} {\end{leftbar}\end{conv}} \newtheorem{quest}[theo]{Question} \newenvironment{question}[1][] {\begin{quest}[#1]\begin{leftbar}} {\end{leftbar}\end{quest}} \newtheorem{warn}[theo]{Warning} \newenvironment{conclusion}[1][] {\begin{warn}[#1]\begin{leftbar}} {\end{leftbar}\end{warn}} \newtheorem{conj}[theo]{Conjecture} \newenvironment{conjecture}[1][] {\begin{conj}[#1]\begin{leftbar}} {\end{leftbar}\end{conj}} \newtheorem{exam}[theo]{Example} \newenvironment{example}[1][] {\begin{exam}[#1]\begin{leftbar}} {\end{leftbar}\end{exam}} \newtheorem{exmp}[exer]{Exercise} \newenvironment{exercise}[1][] {\begin{exmp}[#1]\begin{leftbar}} {\end{leftbar}\end{exmp}} \newenvironment{statement}{\begin{quote}}{\end{quote}} \newenvironment{fineprint}{\begin{small}}{\end{small}} \iffalse \newenvironment{proof}[1][Proof]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}} \newenvironment{convention}[1][Convention]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}} \newenvironment{question}[1][Question]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}} \fi \let\sumnonlimits\sum \let\prodnonlimits\prod \let\cupnonlimits\bigcup \let\capnonlimits\bigcap \renewcommand{\sum}{\sumnonlimits\limits} \renewcommand{\prod}{\prodnonlimits\limits} \renewcommand{\bigcup}{\cupnonlimits\limits} \renewcommand{\bigcap}{\capnonlimits\limits} \setlength\tablinesep{3pt} \setlength\arraylinesep{3pt} \setlength\extrarulesep{3pt} \setlength\textheight{22.5cm} \setlength\textwidth{14.8cm} \newenvironment{verlong}{}{} \newenvironment{vershort}{}{} \newenvironment{noncompile}{}{} \excludecomment{verlong} \includecomment{vershort} \excludecomment{noncompile} \newcommand{\defn}[1]{{\color{darkred}\emph{#1}}} \newcommand{\PER}{\operatorname{PER}} \newcommand{\PD}{\operatorname{PD}} \newcommand{\proj}{\operatorname{proj}} \newcommand{\CC}{\mathbb{C}} \newcommand{\RR}{\mathbb{R}} \newcommand{\QQ}{\mathbb{Q}} \newcommand{\NN}{\mathbb{N}} \newcommand{\ZZ}{\mathbb{Z}} \newcommand{\KK}{\mathbb{K}} \newcommand{\PPos}{\RR_{>0}} \newcommand{\set}[1]{\left\{ #1 \right\}} \newcommand{\abs}[1]{\left| #1 \right|} \newcommand{\tup}[1]{\left( #1 \right)} \newcommand{\ive}[1]{\left[ #1 \right]} \newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor} \newcommand{\calF}{\mathcal{F}} \newcommand{\calB}{\mathcal{B}} \newcommand{\IN}{\ive{N}} \newcommand{\Eh}{\widehat{E}} \newcommand{\wh}{\widehat{w}} \renewcommand{\dh}{\widehat{d}} \newcommand{\Ch}{\widehat{C}} \newcommand{\timesu}{\mathbin{\underline{\times}}} \newcommand{\verts}[1]{\operatorname{V}\left( #1 \right)} \newcommand{\edges}[1]{\operatorname{E}\left( #1 \right)} \renewcommand{\leq}{\leqslant} \renewcommand{\geq}{\geqslant} \renewcommand{\subset}{\subseteq} \iffalse \NOEXPAND{\timesu}{\mathbin{\underline{\times}}} \fi \newcommand{\nuo}{\nu^{\circ}} \newtheoremstyle{plainsl} {8pt plus 2pt minus 4pt} {8pt plus 2pt minus 4pt} {\slshape} {0pt} {\bfseries} {.} {5pt plus 1pt minus 1pt} {} \theoremstyle{plainsl} \ihead{The Elser nuclei sum revisited} \ohead{page \thepage} \cfoot{} \begin{document} \title{The Elser nuclei sum revisited} \author{Darij Grinberg\thanks{Drexel University, Korman Center, Room 291, 15 S 33rd Street, Philadelphia PA, 19104, USA}} \date{version 1.1 (corrected version of arXiv:2009.11527v1), \today} \maketitle \begin{abstract} \textbf{Abstract.} Fix a finite undirected graph $G$ and a vertex $v$ of $G$. Let $E$ be the set of edges of $G$; assume that $E\neq\varnothing$. We call a subset $F$ of $E$ \textit{pandemic} if each edge of $G$ has at least one endpoint that can be connected to $v$ by an $F$-path (i.e., a path using edges from $F$ only). In 1984, Elser showed that the sum of $\left( -1\right) ^{\left\vert F\right\vert }$ over all pandemic subsets $F$ of $E$ is $0$. We give a simpler proof and discuss variants and generalizations. \end{abstract} \section*{****} In \cite{Elser84}, Veit Elser studied the probabilities of clusters forming when $n$ points are sampled randomly in a $d$-dimensional volume. In the process, he found a purely graph-theoretical lemma \cite[Lemma 1]{Elser84}, which served a crucial role in his work. For decades, the lemma stayed hidden from the eyes of combinatorialists in a physics journal, until it resurfaced in recent work \cite{DHLetc19} by Dorpalen-Barry, Hettle, Livingston, Martin, Nasr, Vega and Whitlatch. In this note, I will show a simpler proof of the lemma that illustrates the use of the inclusion-exclusion principle and also suggests a mysterious generalization. \section{Elser's result} Let us first introduce our setting, which is slightly more general (and perhaps also simpler) than that used in \cite{Elser84}. We fix an arbitrary graph $\Gamma$ with vertex set $V$ and edge set $E$. Here, \textquotedblleft graph\textquotedblright\ means \textquotedblleft finite undirected multigraph\textquotedblright\ -- i.e., it can have self-loops and parallel edges, but it has finitely many vertices and edges, and its edges are undirected. We fix a vertex $v\in V$. If $F\subseteq E$, then an $F$\emph{-path} shall mean a path of $\Gamma$ such that all edges of the path belong to $F$. If $e\in E$ is any edge and $F\subseteq E$ is any subset, then we say that $F$ \emph{infects }$e$ if there exists an $F$-path from $v$ to some endpoint of $e$. (The terminology is inspired by the idea of an infectious disease starting in the vertex $v$ and being transmitted along edges.)\footnote{Note that if an edge $e$ contains the vertex $v$, then any subset $F$ of $E$ (even the empty one) infects $e$, since there is a trivial (edgeless) $F$-path from $v$ to $v$.} A subset $F\subseteq E$ is said to be \emph{pandemic} if it infects each edge $e\in E$. \begin{example} \label{exa.example1} Let $\Gamma$ be the following graph:% \[% %TCIMACRO{\TeXButton{graph with 6 vertices and 8 edges}{\begin{tikzpicture}% %[-,>=stealth',shorten >=1pt,auto,node distance=3cm, thick,main node/.style={circle,fill=blue!20,draw}% %] %\node[main node] (1) {$v$}; %\node[main node] [above of=1] (2) {$p$}; %\node[main node] [right of=1] (3) {$w$}; %\node[main node] [above of=3] (4) {$q$}; %\node[main node] [right of=3] (5) {$t$}; %\node[main node] [above of=5] (6) {$r$}; %\path[every node/.style={font=\sffamily\small}] (1) edge node {$1$} %(2) (2) edge node {$2$} (4) (4) edge node {$3$} %(6) (6) edge [bend left] node {$4$} (5) (5) edge node {$5$} %(3) (3) edge node {$6$} (1) (5) edge [bend left] node {$7$} %(6) (4) edge node {$8$} (3); %\end{tikzpicture}}}% %BeginExpansion \begin{tikzpicture}% [-,>=stealth',shorten >=1pt,auto,node distance=3cm, thick,main node/.style={circle,fill=blue!20,draw}% ] \node[main node] (1) {$v$}; \node[main node] [above of=1] (2) {$p$}; \node[main node] [right of=1] (3) {$w$}; \node[main node] [above of=3] (4) {$q$}; \node[main node] [right of=3] (5) {$t$}; \node[main node] [above of=5] (6) {$r$}; \path[every node/.style={font=\sffamily\small}] (1) edge node {$1$} (2) (2) edge node {$2$} (4) (4) edge node {$3$} (6) (6) edge [bend left] node {$4$} (5) (5) edge node {$5$} (3) (3) edge node {$6$} (1) (5) edge [bend left] node {$7$} (6) (4) edge node {$8$} (3); \end{tikzpicture}% %EndExpansion \] (where the vertex $v$ is the vertex labelled $v$). Then, for example, the set $\left\{ 1,2\right\} \subseteq E$ infects edges $1,2,3,6,8$ (but none of the other edges). The set $\left\{ 1,2,5\right\} $ infects the same edges as $\left\{ 1,2\right\} $ (indeed, the additional edge $5$ does not increase its infectiousness, since it is not on any $\left\{ 1,2,5\right\} $-path from $v$). The set $\left\{ 1,2,3\right\} $ infects every edge other than $5$. The set $\left\{ 1,2,3,4\right\} $ infects each edge, and thus is pandemic. \end{example} Now, we can state our version of \cite[Lemma 1]{Elser84}: \begin{theorem} \label{thm.elser0}Assume that $E\neq\varnothing$. Then,% \begin{equation} \sum_{\substack{F\subseteq E\text{ is}\\\text{pandemic}}}\left( -1\right) ^{\left\vert F\right\vert }=0. \label{eq.thm.elser0.eq}% \end{equation} \end{theorem} \begin{example} \label{exa.example2} Let $\Gamma$ be the following graph:% \[% %TCIMACRO{\TeXButton{C4 graph}{\begin{tikzpicture}% %[-,>=stealth',shorten >=1pt,auto,node distance=3cm, thick,main node/.style={circle,fill=blue!20,draw}% %] %\node[main node] (1) {$v$}; %\node[main node] [above of=1] (2) {$p$}; %\node[main node] [right of=2] (3) {$q$}; %\node[main node] [right of=1] (4) {$w$}; %\path[every node/.style={font=\sffamily\small}] (1) edge node {$1$} %(2) (2) edge node {$2$} (3) (3) edge node {$3$} (4) (4) edge node {$4$} (1); %\end{tikzpicture}}}% %BeginExpansion \begin{tikzpicture}% [-,>=stealth',shorten >=1pt,auto,node distance=3cm, thick,main node/.style={circle,fill=blue!20,draw}% ] \node[main node] (1) {$v$}; \node[main node] [above of=1] (2) {$p$}; \node[main node] [right of=2] (3) {$q$}; \node[main node] [right of=1] (4) {$w$}; \path[every node/.style={font=\sffamily\small}] (1) edge node {$1$} (2) (2) edge node {$2$} (3) (3) edge node {$3$} (4) (4) edge node {$4$} (1); \end{tikzpicture}% %EndExpansion \] (where the vertex $v$ is the vertex labelled $v$). Then, the pandemic subsets of $E$ are the sets% \[ \left\{ 1,2\right\} ,\ \ \left\{ 1,4\right\} ,\ \ \left\{ 3,4\right\} ,\ \ \left\{ 1,2,3\right\} ,\ \ \left\{ 1,3,4\right\} ,\ \ \left\{ 1,2,4\right\} ,\ \ \left\{ 2,3,4\right\} ,\ \ \left\{ 1,2,3,4\right\} . \] The sizes of these subsets are $2,2,2,3,3,3,3,4$, respectively. Hence, (\ref{eq.thm.elser0.eq}) says that% \[ \left( -1\right) ^{2}+\left( -1\right) ^{2}+\left( -1\right) ^{2}+\left( -1\right) ^{3}+\left( -1\right) ^{3}+\left( -1\right) ^{3}+\left( -1\right) ^{3}+\left( -1\right) ^{4}=0. \] \end{example} We note that the equality (\ref{eq.thm.elser0.eq}) can be restated as \textquotedblleft there are equally many pandemic subsets $F\subseteq E$ of even size and pandemic subsets $F\subseteq E$ of odd size\textquotedblright. Thus, in particular, the number of all pandemic subsets $F$ of $E$ is even (when $E\neq\varnothing$). \begin{remark} Theorem \ref{thm.elser0} is a bit more general than \cite[Lemma 1]{Elser84}. To see why, we assume that the graph $\Gamma$ is connected and simple (i.e., has no self-loops and parallel edges). Then, a \textit{nucleus} is defined in \cite{Elser84} as a subgraph $N$ of $\Gamma$ with the properties that \begin{enumerate} \item the subgraph $N$ is connected, and \item each edge of $\Gamma$ has at least one endpoint in $N$. \end{enumerate} \noindent Given a subgraph $N$ of $\Gamma$, we let $\operatorname*{E}\left( N\right) $ denote the set of all edges of $N$. Now, \cite[Lemma 1]{Elser84} claims that if $E\neq\varnothing$, then% \[ \sum_{\substack{N\text{ is a nucleus}\\\text{containing }v}}\left( -1\right) ^{\left\vert \operatorname*{E}\left( N\right) \right\vert }=0. \] But this is equivalent to (\ref{eq.thm.elser0.eq}), because there is a bijection% \begin{align*} \left\{ \text{nuclei containing }v\right\} & \rightarrow\left\{ \text{pandemic subsets }F\subseteq E\right\} ,\\ N & \mapsto\operatorname*{E}\left( N\right) . \end{align*} We leave it to the reader to check this in detail; what needs to be checked are the following three statements: \begin{itemize} \item If $N$ is a nucleus containing $v$, then $\operatorname*{E}\left( N\right) $ is a pandemic subset of $E$. \item Every nucleus $N$ containing $v$ is uniquely determined by the set $\operatorname*{E}\left( N\right) $. (Indeed, since a nucleus has to be connected, each of its vertices must be an endpoint of one of its edges, unless its only vertex is $v$.) \item If $F$ is a pandemic subset of $E$, then there is a nucleus $N$ containing $v$ such that $\operatorname*{E}\left( N\right) =F$. (Indeed, $N$ can be defined as the subgraph of $\Gamma$ whose vertices are the endpoints of all edges in $F$ as well as the vertex $v$, and whose edges are the edges in $F$. To see that this subgraph $N$ is connected, it suffices to argue that each of its vertices has a path to $v$; but this follows from the definition of \textquotedblleft pandemic\textquotedblright, since each vertex of $N$ other than $v$ belongs to at least one edge in $F$.) \end{itemize} Thus, Theorem \ref{thm.elser0} is equivalent to \cite[Lemma 1]{Elser84} in the case when $\Gamma$ is connected and simple. \end{remark} \begin{remark} It might appear more natural to talk about a subset $F\subseteq E$ infecting a vertex rather than an edge. (Namely, we can say that $F$ infects a vertex $w$ if there is an $F$-path from $v$ to $w$.) However, the analogue of Theorem \ref{thm.elser0} in which pandemicity is defined via infecting all vertices is not true. The graph of Example \ref{exa.example2} provides a counterexample. \end{remark} \section{The proof} Our proof of Theorem \ref{thm.elser0} will rest on a few lemmas. The first is one of the simplest facts in enumerative combinatorics: \begin{lemma} \label{lem.toggle}Let $U$ be a finite set with $U\neq\varnothing$. Then,% \[ \sum_{F\subseteq U}\left( -1\right) ^{\left\vert F\right\vert }=0. \] \end{lemma} We shall prove Lemma \ref{lem.toggle} via a more general result, which we will also use. To state it, we need a definition: \begin{definition} Let $U$ be a set. Let $\mathcal{S}$ be a set of subsets of $U$. Let $u\in U$. We say that $u$ is \emph{toggleable} in $\mathcal{S}$ if the following two statements hold: \begin{itemize} \item For every $F\in\mathcal{S}$ satisfying $u\notin F$, we have $F\cup\left\{ u\right\} \in\mathcal{S}$. \item For every $F\in\mathcal{S}$ satisfying $u\in F$, we have $F\setminus \left\{ u\right\} \in\mathcal{S}$. \end{itemize} \end{definition} Now, we can generalize Lemma \ref{lem.toggle} as follows: \begin{lemma} \label{lem.toggle-gen}Let $U$ be a finite set. Let $\mathcal{S}$ be a set of subsets of $U$. Let $u\in U$ be toggleable in $\mathcal{S}$. Then,% \[ \sum_{F\in\mathcal{S}}\left( -1\right) ^{\left\vert F\right\vert }=0. \] \end{lemma} \begin{proof} [Proof of Lemma \ref{lem.toggle-gen}.]For every $F\in\mathcal{S}$ satisfying $u\notin F$, we have $F\cup\left\{ u\right\} \in\mathcal{S}$ (since $u$ is toggleable in $\mathcal{S}$) and $u\in F\cup\left\{ u\right\} $. Hence, the map% \begin{align*} \Phi:\left\{ F\in\mathcal{S}\ \mid\ u\notin F\right\} & \rightarrow \left\{ F\in\mathcal{S}\ \mid\ u\in F\right\} ,\\ F & \mapsto F\cup\left\{ u\right\} \end{align*} is well-defined. Consider this map $\Phi$. For every $F\in\mathcal{S}$ satisfying $u\in F$, we have $F\setminus\left\{ u\right\} \in\mathcal{S}$ (since $u$ is toggleable in $\mathcal{S}$) and $u\notin F\setminus\left\{ u\right\} $. Hence, the map% \begin{align*} \Psi:\left\{ F\in\mathcal{S}\ \mid\ u\in F\right\} & \rightarrow\left\{ F\in\mathcal{S}\ \mid\ u\notin F\right\} ,\\ F & \mapsto F\setminus\left\{ u\right\} \end{align*} is well-defined. Consider this map $\Psi$. The maps $\Phi$ and $\Psi$ we just defined are clearly mutually inverse. Thus, they are bijections. Hence, in particular, $\Psi$ is a bijection. Thus, we can substitute $\Psi\left( F\right) $ for $F$ in the sum $\sum_{\substack{F\in \mathcal{S};\\u\notin F}}\left( -1\right) ^{\left\vert F\right\vert }$. We thus obtain% \begin{align*} \sum_{\substack{F\in\mathcal{S};\\u\notin F}}\left( -1\right) ^{\left\vert F\right\vert } & =\sum_{\substack{F\in\mathcal{S};\\u\in F}% }\underbrace{\left( -1\right) ^{\left\vert \Psi\left( F\right) \right\vert }}_{\substack{=\left( -1\right) ^{\left\vert F\setminus\left\{ u\right\} \right\vert }\\\text{(since }\Psi\left( F\right) =F\setminus\left\{ u\right\} \\\text{(by the definition of }\Psi\text{))}}}=\sum_{\substack{F\in \mathcal{S};\\u\in F}}\underbrace{\left( -1\right) ^{\left\vert F\setminus\left\{ u\right\} \right\vert }}_{\substack{=\left( -1\right) ^{\left\vert F\right\vert -1}\\\text{(since }\left\vert F\setminus\left\{ u\right\} \right\vert =\left\vert F\right\vert -1\\\text{(because }u\in F\text{))}}}\\ & =\sum_{\substack{F\in\mathcal{S};\\u\in F}}\underbrace{\left( -1\right) ^{\left\vert F\right\vert -1}}_{=-\left( -1\right) ^{\left\vert F\right\vert }}=-\sum_{\substack{F\in\mathcal{S};\\u\in F}}\left( -1\right) ^{\left\vert F\right\vert }. \end{align*} But each $F\in\mathcal{S}$ satisfies either $u\in F$ or $u\notin F$ (but not both). Hence,% \[ \sum_{F\in\mathcal{S}}\left( -1\right) ^{\left\vert F\right\vert }% =\sum_{\substack{F\in\mathcal{S};\\u\in F}}\left( -1\right) ^{\left\vert F\right\vert }+\underbrace{\sum_{\substack{F\in\mathcal{S};\\u\notin F}}\left( -1\right) ^{\left\vert F\right\vert }}_{=-\sum_{\substack{F\in \mathcal{S};\\u\in F}}\left( -1\right) ^{\left\vert F\right\vert }}% =\sum_{\substack{F\in\mathcal{S};\\u\in F}}\left( -1\right) ^{\left\vert F\right\vert }-\sum_{\substack{F\in\mathcal{S};\\u\in F}}\left( -1\right) ^{\left\vert F\right\vert }=0. \] This proves Lemma \ref{lem.toggle-gen}. \end{proof} \begin{proof} [Proof of Lemma \ref{lem.toggle}.]We have $U\neq\varnothing$; hence, there exists some $u\in U$. Consider this $u$. Let $\mathcal{S}$ be the entire power set of $U$. Then, $u$ is toggleable in $\mathcal{S}$ (for obvious reasons). Hence, Lemma \ref{lem.toggle-gen} yields $\sum_{F\in\mathcal{S}}\left( -1\right) ^{\left\vert F\right\vert }=0$. But $\sum_{F\in\mathcal{S}}\left( -1\right) ^{\left\vert F\right\vert }% =\sum_{F\subseteq U}\left( -1\right) ^{\left\vert F\right\vert }$ (since $\mathcal{S}$ is the entire power set of $U$). Comparing the last two equalities, we obtain $\sum_{F\subseteq U}\left( -1\right) ^{\left\vert F\right\vert }=0$. This proves Lemma \ref{lem.toggle}. \end{proof} Theorem \ref{thm.elser0} is about a sum over all pandemic subsets of $E$ -- that is, all subsets of $E$ that infect every edge in $E$. We shall consider this sum as part of a family of sums $A\left( P\right) $, indexed over all subsets $P$ of $E$: \begin{definition} \label{def.APNP}For any subset $P$ of $E$, we define two subsets% \[ A\left( P\right) =\left\{ F\subseteq E\ \mid\ F\text{ infects each }p\in P\right\} \] and% \[ N\left( P\right) =\left\{ F\subseteq E\ \mid\ F\text{ infects no }p\in P\right\} \] of the power set of $E$. \end{definition} \begin{lemma} \label{lem.APNP}Let $G$ be a subset of $E$. Then,% \[ \sum_{F\in A\left( G\right) }\left( -1\right) ^{\left\vert F\right\vert }=\sum_{P\subseteq G}\left( -1\right) ^{\left\vert P\right\vert }\sum_{F\in N\left( P\right) }\left( -1\right) ^{\left\vert F\right\vert }. \] \end{lemma} \begin{proof} [Proof of Lemma \ref{lem.APNP}.]For any subset $F$ of $E$, we let% \[ X\left( F\right) =\left\{ e\in G\ \mid\ F\text{ does not infect }e\right\} . \] This $X\left( F\right) $ is always a subset of $G$. For any subset $F\subseteq E$ and every set $P$, we have the following chain of equivalences:% \begin{align*} & \ \left( P\subseteq X\left( F\right) \right) \\ & \Longleftrightarrow\ \left( \text{each }p\in P\text{ belongs to }X\left( F\right) \right) \\ & \Longleftrightarrow\ \left( \text{each }p\in P\text{ is an }e\in G\text{ with the property that }F\text{ does not infect }e\right) \\ & \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \left( \text{by the definition of }X\left( F\right) \right) \\ & \Longleftrightarrow\ \left( \text{each }p\in P\text{ belongs to }G\text{ and has the property that }F\text{ does not infect }p\right) \\ & \Longleftrightarrow\ \underbrace{\left( \text{each }p\in P\text{ belongs to }G\right) }_{\Longleftrightarrow\ \left( P\subseteq G\right) }% \wedge\left( F\text{ infects no }p\in P\right) \\ & \Longleftrightarrow\ \left( P\subseteq G\right) \wedge\left( F\text{ infects no }p\in P\right) . \end{align*} Thus, for any subset $F\subseteq E$, we have the following equality of summation signs:% \begin{equation} \sum_{P\subseteq X\left( F\right) }=\sum_{\substack{P\subseteq G;\\F\text{ infects no }p\in P}}\ . \label{pf.lem.APNP.sum=sum1}% \end{equation} Moreover, for any subset $F\subseteq E$, we have the following chain of equivalences:% \begin{align} & \ \left( X\left( F\right) =\varnothing\right) \nonumber\\ & \Longleftrightarrow\ \left( \text{there exists no element of }X\left( F\right) \right) \nonumber\\ & \Longleftrightarrow\ \left( \text{there exists no }e\in G\text{ such that }F\text{ does not infect }e\right) \nonumber\\ & \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \left( \text{by the definition of }X\left( F\right) \right) \nonumber\\ & \Longleftrightarrow\ \left( F\text{ infects each }e\in G\right) \nonumber\\ & \Longleftrightarrow\ \left( F\text{ infects each }p\in G\right) \nonumber\\ & \Longleftrightarrow\ \left( F\in A\left( G\right) \right) \ \ \ \ \ \ \ \ \ \ \left( \text{by the definition of }A\left( G\right) \right) . \label{pf.lem.APNP.sum=sum2equiv}% \end{align} Now, we have% \begin{align*} & \sum_{P\subseteq G}\left( -1\right) ^{\left\vert P\right\vert }\underbrace{\sum_{F\in N\left( P\right) }}_{\substack{=\sum _{\substack{F\subseteq E;\\F\text{ infects no }p\in P}}\\\text{(by the definition of }N\left( P\right) \text{)}}}\left( -1\right) ^{\left\vert F\right\vert }\\ & =\sum_{P\subseteq G}\left( -1\right) ^{\left\vert P\right\vert }% \sum_{\substack{F\subseteq E;\\F\text{ infects no }p\in P}}\left( -1\right) ^{\left\vert F\right\vert }=\underbrace{\sum_{P\subseteq G}\sum _{\substack{F\subseteq E;\\F\text{ infects no }p\in P}}}_{=\sum_{F\subseteq E}\sum_{\substack{P\subseteq G;\\F\text{ infects no }p\in P}}}\left( -1\right) ^{\left\vert P\right\vert }\left( -1\right) ^{\left\vert F\right\vert }\\ & =\sum_{F\subseteq E}\underbrace{\sum_{\substack{P\subseteq G;\\F\text{ infects no }p\in P}}}_{\substack{=\sum_{P\subseteq X\left( F\right) }\\\text{(by (\ref{pf.lem.APNP.sum=sum1}))}}}\left( -1\right) ^{\left\vert P\right\vert }\left( -1\right) ^{\left\vert F\right\vert }=\sum_{F\subseteq E}\ \ \sum_{P\subseteq X\left( F\right) }\left( -1\right) ^{\left\vert P\right\vert }\left( -1\right) ^{\left\vert F\right\vert }\\ & =\sum_{Q\subseteq E}\ \ \sum_{F\subseteq X\left( Q\right) }\left( -1\right) ^{\left\vert F\right\vert }\left( -1\right) ^{\left\vert Q\right\vert }\ \ \ \ \ \ \ \ \ \ \left( \begin{array} [c]{c}% \text{here, we renamed the}\\ \text{summation indices }F\text{ and }P\\ \text{as }Q\text{ and }F\text{, respectively}% \end{array} \right) \\ & =\sum_{\substack{Q\subseteq E;\\X\left( Q\right) =\varnothing }}\underbrace{\sum_{F\subseteq X\left( Q\right) }\left( -1\right) ^{\left\vert F\right\vert }}_{\substack{=\sum_{F\subseteq\varnothing}\left( -1\right) ^{\left\vert F\right\vert }\\\text{(since }X\left( Q\right) =\varnothing\text{)}}}\left( -1\right) ^{\left\vert Q\right\vert }% +\sum_{\substack{Q\subseteq E;\\X\left( Q\right) \neq\varnothing }}\underbrace{\sum_{F\subseteq X\left( Q\right) }\left( -1\right) ^{\left\vert F\right\vert }}_{\substack{=0\\\text{(by Lemma \ref{lem.toggle}% ,}\\\text{applied to }U=X\left( Q\right) \text{)}}}\left( -1\right) ^{\left\vert Q\right\vert }\\ & \ \ \ \ \ \ \ \ \ \ \left( \begin{array} [c]{c}% \text{since each subset }Q\text{ of }E\text{ satisfies either }X\left( Q\right) =\varnothing\\ \text{or }X\left( Q\right) \neq\varnothing\text{ (but not both)}% \end{array} \right) \end{align*}% \begin{align*} & =\sum_{\substack{Q\subseteq E;\\X\left( Q\right) =\varnothing }}\underbrace{\sum_{F\subseteq\varnothing}\left( -1\right) ^{\left\vert F\right\vert }}_{=\left( -1\right) ^{\left\vert \varnothing\right\vert }=\left( -1\right) ^{0}=1}\left( -1\right) ^{\left\vert Q\right\vert }+\underbrace{\sum_{\substack{Q\subseteq E;\\X\left( Q\right) \neq \varnothing}}0\left( -1\right) ^{\left\vert Q\right\vert }}_{=0}\\ & =\sum_{\substack{Q\subseteq E;\\X\left( Q\right) =\varnothing}}\left( -1\right) ^{\left\vert Q\right\vert }=\underbrace{\sum_{\substack{F\subseteq E;\\X\left( F\right) =\varnothing}}}_{\substack{=\sum_{\substack{F\subseteq E;\\F\in A\left( G\right) }}\\\text{(by (\ref{pf.lem.APNP.sum=sum2equiv}))}% }}\left( -1\right) ^{\left\vert F\right\vert }=\underbrace{\sum _{\substack{F\subseteq E;\\F\in A\left( G\right) }}}_{\substack{=\sum_{F\in A\left( G\right) }\\\text{(since}\\\text{every }F\in A\left( G\right) \\\text{satisfies }F\subseteq E\text{)}}}\left( -1\right) ^{\left\vert F\right\vert }=\sum_{F\in A\left( G\right) }\left( -1\right) ^{\left\vert F\right\vert }. \end{align*} This proves Lemma \ref{lem.APNP}. \end{proof} So far, we have used nothing about graphs and infection; Lemma \ref{lem.APNP} does not depend on any property of the \textquotedblleft infects\textquotedblright\ relation other than it being a relation between subsets of $E$ and elements of $E$. Actually, Lemma \ref{lem.APNP} can be viewed as an instance of the Principle of Inclusion and Exclusion, or of M\"{o}bius inversion of the Boolean lattice; a reader familiar with these results will easily find a way to derive it from them.\footnote{See \cite{Rota64}, \cite[Sections 2.1--2.3]{Sagan19}, \cite[Chapter 2]% {Stanley-EC1}, \cite{BenQui08}, \cite[Chapter 5]{Aigner07} for various aspects of this theory. For example, Lemma \ref{lem.APNP} can be obtained as a particular case of \cite[Chapter 5, (16)]{Aigner07}.} We found it easier to prove Lemma \ref{lem.APNP} from scratch, however, particularly since the main auxiliary result (Lemma \ref{lem.toggle-gen}) will be needed again anyway. The next lemma (which, unlike the previous ones, does rely on the actual nature of \textquotedblleft infection\textquotedblright) shows that the sums $\sum_{F\in N\left( P\right) }\left( -1\right) ^{\left\vert F\right\vert }$ in Lemma \ref{lem.APNP} are almost always $0$: \begin{lemma} \label{lem.NP}We have the following: \begin{enumerate} \item[\textbf{(a)}] Every nonempty set $P$ of $E$ satisfies% \[ \sum_{F\in N\left( P\right) }\left( -1\right) ^{\left\vert F\right\vert }=0. \] \item[\textbf{(b)}] If $E\neq\varnothing$, then every subset $P$ of $E$ satisfies% \[ \sum_{F\in N\left( P\right) }\left( -1\right) ^{\left\vert F\right\vert }=0. \] \end{enumerate} \end{lemma} In order to prove this, we will need the following: \begin{lemma} \label{lem.NP-tog}Let $P$ be a subset of $E$. Let $u\in P$. Then, $u$ is toggleable in $N\left( P\right) $. \end{lemma} \begin{proof} [Proof of Lemma \ref{lem.NP-tog}.]We must prove the following two claims: \begin{statement} \textit{Claim 1:} For every $F\in N\left( P\right) $ satisfying $u\notin F$, we have $F\cup\left\{ u\right\} \in N\left( P\right) $. \end{statement} \begin{statement} \textit{Claim 2:} For every $F\in N\left( P\right) $ satisfying $u\in F$, we have $F\setminus\left\{ u\right\} \in N\left( P\right) $. \end{statement} [\textit{Proof of Claim 1:} Let $F\in N\left( P\right) $ satisfy $u\notin F$. We must show that $F\cup\left\{ u\right\} \in N\left( P\right) $. We have $F\in N\left( P\right) $. In other words, $F$ is a subset of $E$ that infects no $p\in P$. Thus, $F\cup\left\{ u\right\} $ is a subset of $E$ (since $F\subseteq E$ and $u\in P\subseteq E$). Now we claim that $F\cup\left\{ u\right\} $ infects no $p\in P$. Indeed, assume the contrary. Then, $F\cup\left\{ u\right\} $ infects some $p\in P$. In other words, $F\cup\left\{ u\right\} $ infects some $q\in P$. In other words, there exists some $q\in P$ such that $F\cup\left\{ u\right\} $ infects $q$. Consider this $q$. Note that $F$ does not infect $q$ (since $F$ infects no $p\in P$). In other words, there exists no $F$-path from $v$ to any endpoint of $q$ (by the definition of \textquotedblleft infects\textquotedblright). We know that $F\cup\left\{ u\right\} $ infects $q$. In other words, there exists an $\left( F\cup\left\{ u\right\} \right) $-path from $v$ to some endpoint of $q$ (by the definition of \textquotedblleft infects\textquotedblright). Let $\pi$ be this path. If this $\left( F\cup\left\{ u\right\} \right) $-path $\pi$ did not contain the edge $u$, then it would be an $F$-path, which would contradict the fact that there exists no $F$-path from $v$ to any endpoint of $q$. Hence, this $\left( F\cup\left\{ u\right\} \right) $-path $\pi$ must contain the edge $u$. By removing $u$, we can thus cut this path $\pi$ into two segments: The first segment is a path from $v$ to some endpoint of $u$, while the second segment is a path from the other endpoint of $u$ to some endpoint of $q$. Both segments are $F$-paths (since they arise by removing $u$ from an $\left( F\cup\left\{ u\right\} \right) $-path). Thus, in particular, the first segment is an $F$-path from $v$ to some endpoint of $u$. Hence, there exists an $F$-path from $v$ to some endpoint of $u$. In other words, $F$ infects $u$ (by the definition of \textquotedblleft infects\textquotedblright). But we have $u\in P$; hence, $F$ does not infect $u$ (since $F$ infects no $p\in P$). This contradicts the fact that $F$ infects $u$. This contradiction shows that our assumption was false. Hence, we have shown that $F\cup\left\{ u\right\} $ infects no $p\in P$. In other words, $F\cup\left\{ u\right\} \in N\left( P\right) $ (by the definition of $N\left( P\right) $). This proves Claim 1.] [\textit{Proof of Claim 2:} Let $F\in N\left( P\right) $ satisfy $u\in F$. We must show that $F\setminus\left\{ u\right\} \in N\left( P\right) $. We have $F\in N\left( P\right) $. In other words, $F$ is a subset of $E$ that infects no $p\in P$. Thus, $F\setminus\left\{ u\right\} $ is a subset of $E$ (since $F\subseteq E$). Now we claim that $F\setminus\left\{ u\right\} $ infects no $p\in P$. Indeed, assume the contrary. Then, $F\setminus\left\{ u\right\} $ infects some $p\in P$. In other words, $F\setminus\left\{ u\right\} $ infects some $q\in P$. In other words, there exists some $q\in P$ such that $F\setminus \left\{ u\right\} $ infects $q$. Consider this $q$. Note that $F$ does not infect $q$ (since $F$ infects no $p\in P$). We know that $F\setminus\left\{ u\right\} $ infects $q$. In other words, there exists an $\left( F\setminus\left\{ u\right\} \right) $-path from $v$ to some endpoint of $q$ (by the definition of \textquotedblleft infects\textquotedblright). Hence, there exists an $F$-path from $v$ to some endpoint of $q$ (since any $\left( F\setminus\left\{ u\right\} \right) $-path is automatically an $F$-path\footnote{because $F\setminus\left\{ u\right\} \subseteq F$}). In other words, $F$ infects $q$ (by the definition of \textquotedblleft infects\textquotedblright). This contradicts the fact that $F$ does not infect $q$. This contradiction shows that our assumption was false. Hence, we have shown that $F\setminus\left\{ u\right\} $ infects no $p\in P$. In other words, $F\setminus\left\{ u\right\} \in N\left( P\right) $ (by the definition of $N\left( P\right) $). This proves Claim 2.] We have now proved both Claim 1 and Claim 2. Hence, we conclude that $u$ is toggleable in $N\left( P\right) $ (by the definition of \textquotedblleft toggleable\textquotedblright). This proves Lemma \ref{lem.NP-tog}. \end{proof} We can now easily obtain Lemma \ref{lem.NP}: \begin{proof} [Proof of Lemma \ref{lem.NP}.]\textbf{(a)} Let $P$ be a nonempty subset of $E$. Then, there exists some $u\in P$ (since $P$ is nonempty). Consider this $u$. Lemma \ref{lem.NP-tog} yields that $u$ is toggleable in $N\left( P\right) $. Thus, Lemma \ref{lem.toggle-gen} (applied to $U=E$ and $\mathcal{S}=N\left( P\right) $) yields% \[ \sum_{F\in N\left( P\right) }\left( -1\right) ^{\left\vert F\right\vert }=0. \] This proves Lemma \ref{lem.NP} \textbf{(a)}. \textbf{(b)} Assume that $E\neq\varnothing$. Let $P$ be a subset of $E$. We must prove that \[ \sum_{F\in N\left( P\right) }\left( -1\right) ^{\left\vert F\right\vert }=0. \] If $P$ is nonempty, then this follows from Lemma \ref{lem.NP} \textbf{(a)}. Thus, we WLOG assume that $P$ is empty. Hence, $N\left( P\right) $ is the entire power set of $E$ (since the condition \textquotedblleft$F$ infects no $p\in P$\textquotedblright\ in the definition of $N\left( P\right) $ is vacuously true when $P$ is empty). Therefore,% \[ \sum_{F\in N\left( P\right) }\left( -1\right) ^{\left\vert F\right\vert }=\sum_{F\subseteq E}\left( -1\right) ^{\left\vert F\right\vert }=0 \] (by Lemma \ref{lem.toggle}, applied to $U=E$). This proves Lemma \ref{lem.NP} \textbf{(b)}. \end{proof} Lemma \ref{lem.NP} easily yields something slightly more general than Theorem \ref{thm.elser0}: \begin{theorem} \label{thm.elser0G}Assume that $E\neq\varnothing$. Let $G$ be a subset of $E$. Then,% \[ \sum_{F\in A\left( G\right) }\left( -1\right) ^{\left\vert F\right\vert }=0. \] \end{theorem} \begin{proof} [Proof of Theorem \ref{thm.elser0G}.]Lemma \ref{lem.APNP} yields% \[ \sum_{F\in A\left( G\right) }\left( -1\right) ^{\left\vert F\right\vert }=\sum_{P\subseteq G}\left( -1\right) ^{\left\vert P\right\vert }\underbrace{\sum_{F\in N\left( P\right) }\left( -1\right) ^{\left\vert F\right\vert }}_{\substack{=0\\\text{(by Lemma \ref{lem.NP} \textbf{(b)})}% }}=\sum_{P\subseteq G}\left( -1\right) ^{\left\vert P\right\vert }0=0. \] This proves Theorem \ref{thm.elser0G}. \end{proof} \begin{proof} [Proof of Theorem \ref{thm.elser0}.]Let $G$ be the set $E$. Thus, $G=E$, so that% \begin{align*} A\left( G\right) & =A\left( E\right) \\ & =\left\{ F\subseteq E\ \mid\ F\text{ infects each }p\in E\right\} \ \ \ \ \ \ \ \ \ \ \left( \text{by the definition of }A\left( E\right) \right) \\ & =\left\{ F\subseteq E\ \mid\ F\text{ infects each }e\in E\right\} =\left\{ F\subseteq E\ \mid\ F\text{ is pandemic}\right\} \end{align*} (by the definition of \textquotedblleft pandemic\textquotedblright). Hence, \[ \sum_{F\in A\left( G\right) }\left( -1\right) ^{\left\vert F\right\vert }=\sum_{\substack{F\subseteq E\text{ is}\\\text{pandemic}}}\left( -1\right) ^{\left\vert F\right\vert }. \] But Theorem \ref{thm.elser0G} yields% \[ \sum_{F\in A\left( G\right) }\left( -1\right) ^{\left\vert F\right\vert }=0. \] Comparing these two equalities, we find \[ \sum_{\substack{F\subseteq E\text{ is}\\\text{pandemic}}}\left( -1\right) ^{\left\vert F\right\vert }=0. \] This proves Theorem \ref{thm.elser0}. \end{proof} \section{Vertex infection and other variants} In our study of graphs so far, we have barely ever mentioned vertices (even though they are, of course, implicit in the notion of a path). It may appear somewhat strange to talk about a subset infecting an edge, when the infection is spread from vertex to vertex. One might thus wonder if there is also a vertex counterpart of Theorem \ref{thm.elser0}. So let us define analogues of our notions for vertices: If $F\subseteq V$, then an $F$\emph{-vertex-path} shall mean a path of $\Gamma$ such that all vertices of the path except (possibly) for its two endpoints belong to $F$. (Thus, if a path has only one edge or none, then it automatically is an $F$-vertex-path.) If $w\in V\setminus\left\{ v\right\} $ is any vertex and $F\subseteq V\setminus\left\{ v\right\} $ is any subset, then we say that $F$ \emph{vertex-infects }$w$ if there exists an $F$-vertex-path from $v$ to $w$. (This is always true when $w$ is $v$ or a neighbor of $v$.) A subset $F\subseteq V\setminus\left\{ v\right\} $ is said to be \emph{vertex-pandemic} if it vertex-infects each vertex $w\in V\setminus \left\{ v\right\} $. \begin{example} Let $\Gamma$ be as in Example \ref{exa.example2}. Then, the path $v\overset{1}{\longrightarrow}p\overset{2}{\longrightarrow}q$ is an $F$-vertex-path for any subset $F\subseteq V$ that satisfies $p\in F$. The subset $\left\{ p\right\} $ of $V\setminus\left\{ v\right\} $ vertex-infects each vertex (for example, $v\overset{1}{\longrightarrow }p\overset{2}{\longrightarrow}q$ is a $\left\{ p\right\} $-vertex-path from $v$ to $q$, and $v\overset{4}{\longrightarrow}w$ is a $\left\{ p\right\} $-vertex-path from $v$ to $w$), and thus is vertex-pandemic. The vertex-pandemic subsets of $V\setminus\left\{ v\right\} $ are the sets% \[ \left\{ p\right\} ,\ \ \left\{ w\right\} ,\ \ \left\{ p,q\right\} ,\ \ \left\{ p,w\right\} ,\ \ \left\{ q,w\right\} ,\ \ \left\{ p,q,w\right\} . \] \end{example} We now have the following analogue of Theorem \ref{thm.elser0}: \begin{theorem} \label{thm.elser0-vert}Assume that $V\setminus\left\{ v\right\} \neq\varnothing$. Then,% \[ \sum_{\substack{F\subseteq V\setminus\left\{ v\right\} \text{ is}% \\\text{vertex-pandemic}}}\left( -1\right) ^{\left\vert F\right\vert }=0. \] \end{theorem} \begin{proof} [Proof of Theorem \ref{thm.elser0-vert}.]With just a few easy modifications, our above proof of Theorem \ref{thm.elser0} can be repurposed as a proof of Theorem \ref{thm.elser0-vert}. Namely: \begin{itemize} \item We need to replace \textquotedblleft edge\textquotedblright\ by \textquotedblleft vertex\textquotedblright\ throughout the argument (including Lemma \ref{lem.APNP}, Lemma \ref{lem.NP}, Lemma \ref{lem.NP-tog} and Theorem \ref{thm.elser0G}), as well as replace $E$ by $V\setminus\left\{ v\right\} $. \item The words \textquotedblleft$F$-path\textquotedblright, \textquotedblleft infects\textquotedblright\ and \textquotedblleft pandemic\textquotedblright% \ have to be replaced by \textquotedblleft$F$-vertex-path\textquotedblright, \textquotedblleft vertex-infects\textquotedblright\ and \textquotedblleft vertex-pandemic\textquotedblright, respectively. \item In the proof of Lemma \ref{lem.NP-tog}, the words \textquotedblleft an endpoint of\textquotedblright\ (as well as \textquotedblleft any endpoint of\textquotedblright\ and \textquotedblleft some endpoint of\textquotedblright% ) need to be removed (since the notion of \textquotedblleft vertex-infects\textquotedblright\ is defined not in terms of paths to an endpoint of a given edge, but in terms of paths to a given vertex). \item In the proof of Lemma \ref{lem.NP-tog}, specifically in the proof of Claim 1, the path $\pi$ is now cut not by removing the edge $u$, but by splitting the path $\pi$ at the vertex $u$. \end{itemize} \noindent The reader may check that these changes result in a valid proof of Theorem \ref{thm.elser0-vert}. \end{proof} Another variant of Theorem \ref{thm.elser0} (and Theorem \ref{thm.elser0G}) is obtained by replacing the undirected graph $\Gamma$ with a directed graph (while, of course, replacing paths by directed paths). More generally, we can replace $\Gamma$ by a \textquotedblleft hybrid\textquotedblright\ graph with some directed and some undirected edges.\footnote{We understand that a directed edge still has two endpoints: its source and its target.} No changes are required to the above proofs. Yet another variation can be obtained by replacing \textquotedblleft endpoint\textquotedblright\ by \textquotedblleft source\textquotedblright\ (for directed edges). We cannot, however, replace \textquotedblleft endpoint\textquotedblright\ by \textquotedblleft target\textquotedblright. \section{An abstract perspective} Seeing how little graph theory we have used in proving Theorem \ref{thm.elser0}, and how easily the same argument adapted to Theorem \ref{thm.elser0-vert}, we get the impression that there might be some general theory lurking behind it. What follows is an attempt at building this theory. Let $\mathcal{P}\left( E\right) $ denote the power set of $E$. The \textquotedblleft infects\textquotedblright\ relation can be encoded as a map $\operatorname*{Shade}:\mathcal{P}\left( E\right) \rightarrow\mathcal{P}% \left( E\right) $ defined by% \[ \operatorname*{Shade}F=\left\{ e\in E\ \mid\ F\text{ infects }e\right\} . \] The definitions of the sets $A\left( P\right) $ and $N\left( P\right) $ in Definition \ref{def.APNP} can thus be rewritten as% \begin{align*} A\left( P\right) & =\left\{ F\subseteq E\ \mid\ P\subseteq \operatorname*{Shade}F\right\} \ \ \ \ \ \ \ \ \ \ \text{and}\\ N\left( P\right) & =\left\{ F\subseteq E\ \mid\ P\cap \operatorname*{Shade}F=\varnothing\right\} . \end{align*} Hence, the claim of Theorem \ref{thm.elser0G} can be rewritten as% \begin{equation} \sum_{\substack{F\subseteq E;\\G\subseteq\operatorname*{Shade}F}}\left( -1\right) ^{\left\vert F\right\vert }=0 \label{eq.Shade.goal}% \end{equation} for any $G\subseteq E$, under the assumption that $E\neq\varnothing$. To generalize this, we forget about the graph $\Gamma$ and the map $\operatorname*{Shade}$, and instead start with an \textbf{arbitrary} finite set $E$. (This corresponds to the set $E$ in Theorem \ref{thm.elser0} and to the set $V\setminus\left\{ v\right\} $ in Theorem \ref{thm.elser0-vert}.) Let $\mathcal{P}\left( E\right) $ be the power set of $E$. Let $\operatorname*{Shade}:\mathcal{P}\left( E\right) \rightarrow\mathcal{P}% \left( E\right) $ be an arbitrary map (meant to generalize the map $\operatorname*{Shade}$ from the previous paragraph). We may now ask: \begin{question} What (combinatorial) properties must $\operatorname*{Shade}$ satisfy in order for (\ref{eq.Shade.goal}) to hold for any $G\subseteq E$ under the assumption that $E\neq\varnothing$ ? \end{question} A partial answer to this question can be given by analyzing our above proof of Theorem \ref{thm.elser0G} and extracting what was used: \begin{theorem} \label{thm.elser.genE0}Let $E$ be a finite set. Let $\operatorname*{Shade}% :\mathcal{P}\left( E\right) \rightarrow\mathcal{P}\left( E\right) $ be an arbitrary map that satisfies the following axioms: \begin{statement} \textit{Axiom 1:} Let $P,F\in\mathcal{P}\left( E\right) $ and $u\in P\setminus F$ be such that $P\cap\operatorname*{Shade}F=\varnothing$. Then, $P\cap\operatorname*{Shade}\left( F\cup\left\{ u\right\} \right) =\varnothing$. \end{statement} \begin{statement} \textit{Axiom 2:} Let $P,F\in\mathcal{P}\left( E\right) $ and $u\in P\cap F$ be such that $P\cap\operatorname*{Shade}F=\varnothing$. Then, $P\cap \operatorname*{Shade}\left( F\setminus\left\{ u\right\} \right) =\varnothing$. \end{statement} Assume that $E\neq\varnothing$. Let $G$ be any subset of $E$. Then,% \[ \sum_{\substack{F\subseteq E;\\G\subseteq\operatorname*{Shade}F}}\left( -1\right) ^{\left\vert F\right\vert }=0. \] \end{theorem} \begin{proof} [Proof sketch.]Again, analogous to our above proof of Theorem \ref{thm.elser0G}. (This time, in the proof of Lemma \ref{lem.NP-tog}, Claim 1 and Claim 2 follow from Axiom 1 and Axiom 2, respectively.) \end{proof} \begin{question} Can the two axioms in Theorem \ref{thm.elser.genE0} be rewritten in a simpler or more transparent way? \end{question} Here is one restatement of both Axioms 1 and 2: For any $F\subseteq E$ and any two elements $u,v\in E\setminus\operatorname*{Shade}F$, we have $v\notin% \operatorname*{Shade}\left( F\cup\left\{ u\right\} \right) $ (Axiom 1) and $v\notin\operatorname*{Shade}\left( F\setminus\left\{ u\right\} \right) $ (Axiom 2). \begin{question} What are examples of maps $\operatorname*{Shade}:\mathcal{P}\left( E\right) \rightarrow\mathcal{P}\left( E\right) $ satisfying the two axioms in Theorem \ref{thm.elser.genE0}? \end{question} We note that the map $\operatorname*{Shade}$ does not have to be monotonic (i.e., it is not necessary that $\operatorname*{Shade}F\subseteq \operatorname*{Shade}G$ whenever $F\subseteq G$). Examples of non-monotonic maps $\operatorname*{Shade}$ that satisfy Axioms 1 and 2 are easily constructed. (Indeed, if $\operatorname*{Shade}:\mathcal{P}\left( E\right) \rightarrow\mathcal{P}\left( E\right) $ is any map satisfying Axioms 1 and 2, then the map $\operatorname*{Shade}\nolimits^{\prime}:\mathcal{P}\left( E\right) \rightarrow\mathcal{P}\left( E\right) $ that sends each $F\in\mathcal{P}\left( E\right) $ to $\operatorname*{Shade}\left( E\setminus F\right) \in\mathcal{P}\left( E\right) $ also satisfies Axioms 1' and 2'; but it is rare for both $\operatorname*{Shade}$ and $\operatorname*{Shade}\nolimits^{\prime}$ to be monotonic.) \subsection*{Acknowledgments} I thank Galen Dorpalen-Barry and Tom Roby for insightful conversations. This research was supported through the programme \textquotedblleft Oberwolfach Leibniz Fellows\textquotedblright\ by the Mathematisches Forschungsinstitut Oberwolfach in 2020. I am deeply grateful to the Institute for its hospitality during a turbulent time. \begin{thebibliography}{99999999} % \bibitem[Aigner07]{Aigner07}% \href{http://doi.org/10.1007/978-3-540-39035-0}{Martin Aigner, \textit{A Course in Enumeration}, Graduate Texts in Mathematics \#238, Springer 2007.} \bibitem[BenQui08]{BenQui08}% \href{https://www.math.hmc.edu/~benjamin/papers/DIE.pdf}{Arthur T. Benjamin and Jennifer J. Quinn, \textit{An Alternate Approach to Alternating Sums: A Method to DIE for}, The College Mathematics Journal, Volume 39, Number 3, May 2008, pp. 191-202(12).} \bibitem[DHLetc19]{DHLetc19}\href{https://arxiv.org/abs/1905.11330v4}{Galen Dorpalen-Barry, Cyrus Hettle, David C. Livingston, Jeremy L. Martin, George Nasr, Julianne Vega, Hays Whitlatch, \textit{A positivity phenomenon in Elser's Gaussian-cluster percolation model}, arXiv:1905.11330v4}. Accepted at Journal of Combinatorial Theory A. \bibitem[Elser84]{Elser84}% \href{https://iopscience.iop.org/article/10.1088/0305-4470/17/7/019/pdf}{Veit Elser, \textit{Gaussian-cluster models of percolation and self-avoiding walks}, J. Phys. A: Math. Gen. \textbf{17} (1984), pp. 1515--1523}. \bibitem[Rota64]{Rota64}\href{https://doi.org/10.1007/BF00531932}{Gian-Carlo Rota, \textit{On the Foundations of Combinatorial Theory I. Theory of M\"{o}bius Functions}, Z. Wahrscheinlichkeitstheorie \textbf{2} (1964), pp. 340--368}. \bibitem[Sagan20]{Sagan19}Bruce Sagan, \textit{Combinatorics: The Art of Counting}, preliminary version, 17 September 2020.\newline\url{https://users.math.msu.edu/users/bsagan/Books/Aoc/final.pdf} \bibitem[Stanle11]{Stanley-EC1}Richard P. Stanley, \textit{Enumerative Combinatorics, volume 1}, 2nd edition, version of 15 July 2011.\newline% \url{http://math.mit.edu/~rstan/ec/} .\newline See \url{http://math.mit.edu/~rstan/ec/} for errata. \end{thebibliography} \end{document}